#include <iostream>
#include <algorithm>

using namespace std;

struct BitNode {
    int val;
    BitNode* lchild;
    BitNode* rchild;
    BitNode(int v, BitNode* lch, BitNode* rch):val(v), lchild(lch), rchild(rch) {};
};

class Solution {
public:
    // pair<int,int> 
    // first: with this node;  second: without this node
    pair<int, int> getMaxSumFromTree(BitNode* root) {
        if(root == nullptr) return pair<int, int>(0, 0);

        auto l_pair = getMaxSumFromTree(root->lchild);
        auto r_pair = getMaxSumFromTree(root->rchild);

        int with_max = root->val + l_pair.second + r_pair.second;
        int without_max = std::max(l_pair.first, l_pair.second) + std::max(r_pair.first, r_pair.second);
        pair<int, int> res = make_pair(with_max, without_max);

        m_max_sum = std::max(res.first, res.second);
        return res;
    }

    int NoAdjacentNodeMaxSum(BitNode *root) {
        if (!root) return 0;

        int sum = 0; // sum with this node
        if (root->lchild)
            sum += NoAdjacentNodeMaxSum(root->lchild->lchild) + NoAdjacentNodeMaxSum(root->lchild->rchild);
        if (root->rchild)
            sum += NoAdjacentNodeMaxSum(root->rchild->lchild) + NoAdjacentNodeMaxSum(root->rchild->rchild);

        // m_max_sum = max(with_this_node, without_this_node);
        int max_with_this_node = sum + root->val;
        int max_without_this_node = NoAdjacentNodeMaxSum(root->lchild) + NoAdjacentNodeMaxSum(root->rchild);
        m_max_sum = std::max(max_with_this_node, max_without_this_node);
        return m_max_sum;
    }
private:
    // record the max sum of no adjacent in the tree.
    int m_max_sum;
};



int main(int argc, char** argv) {

    return 0;
}